package org.chnxi.leetcode.problems.ques5;



import java.util.Arrays;

/**
 * 最长回文子串
 * 执行用时 :385 ms, 在所有 Java 提交中击败了10.13%的用户
 * 内存消耗 :40.5 MB, 在所有 Java 提交中击败了15.18%的用户
 */
public class Simple1 {

    public static void main(String[] args) {
        StringBuilder sb = new StringBuilder();
        for (int i =0 ;i< 1000;i++){
            int num = 0;
            while (true){
                num = (int)(Math.random()*150);
                if(num >= 97 && num<=122){
                    break;
                }
            }
            sb.append((char)num);
        }
        System.out.println(sb.toString());

        //String str = "a";
        String str = "eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee";
        long s1 = System.nanoTime();
        String s = longestPalindrome(sb.toString());
        long s2 = System.nanoTime();
        System.out.println("耗时："+(s2-s1));
        System.out.println("result = "+s);
    }

    public static String longestPalindrome(String s) {
        if(null == s || (s = s.trim()).length() == 0){
            return "";
        }

        char[] chars = s.toCharArray();

        String rs1 = toLeft(chars , s.length()/2);
        String rs2 = toRight(chars,  s.length() /2);
        return rs1.length() > rs2.length() ? rs1 : rs2;
    }

    public static String toLeft(char[] chars, int idx){
        String str = null;
        for (int i=idx; i>=0; i--){

            if(str != null && str.length()/2 >= idx){
                break;
            }

            String tmp = "";
            tmp = isMatch(chars , tmp , i-1 , i);
            if(tmp.length() > (str == null ? 0 : str.length())){
                str = tmp;
            }
            tmp = isMatch(chars , tmp , i , i);
            if(tmp.length() > (str == null ? 0 : str.length())){
                str = tmp;
            }
        }
        return str;
    }

    public static String toRight(char[] chars, int idx){
        String str = null;
        for (int i=idx; i<chars.length; i++){

            if(str != null && str.length()/2 >= idx){
                break;
            }

            String tmp = "";
            tmp = isMatch(chars , tmp , i-1 , i);
            if(tmp.length() > (str == null ? 0 : str.length())){
                str = tmp;
            }
            tmp = isMatch(chars , tmp , i , i);
            if(tmp.length() > (str == null ? 0 : str.length())){
                str = tmp;
            }
        }
        return str;
    }

    public static String isMatch(char[] chars, String str , int leftIdx , int rightIdx){
        //判断是否越界
        if(leftIdx < 0 || rightIdx >= chars.length){
            return str;
        }

        if(chars[leftIdx] == chars[rightIdx]){ //左右两边匹配
            str = String.valueOf(Arrays.copyOfRange(chars , leftIdx , rightIdx+1));
            leftIdx--;
            rightIdx++;

            return isMatch(chars , str , leftIdx , rightIdx);
        }else{
            return str;
        }

    }
}
